用 monoids folding List

Monoid 跟 List 有著相當緊密的關係，Day 4 和 Day5 的 List 中我們有用到 2 個 function，foldLeft 和 foldRight，它們的 function 宣告長這樣，

def foldLeft[B](z: B)(op: (B, A) => B): B
def foldRight[B](z: B)(op: (A, B) => B): B

如果我們讓它們都變成同一個型態 A 呢？

def foldLeft(z: A)(op: (A, A) => A): A
def foldRight(z: A)(op: (A, A) => A): A

此時 Monoid 的組成相當適合這 2 個 function，假設我們有 List[String]，我們可以用 stringMonoid 的 combine 和 empty 來把這些字組合起來，

scala> val words = List("This", " ", "is", " ", "sparta")

scala> val foldLeftResult = words.foldLeft(stringMonoid.empty)(stringMonoid.combine)
val foldLeftResult: String = This is sparta

scala> val foldRightResult = words.foldRight(stringMonoid.empty)(stringMonoid.combine)
val foldRightResult: String = This is sparta

因為結合律的關係，Monoid 下的 foldLeft 和 foldRight 沒有太大區別，所以最後我們可以寫一個 function 來用 Monoid 摺 List，

def combineAll[A](as: List[A], m: Monoid[A]): A =
  as.foldLeft(m.empty)(m.combine)    

但如果我們沒有該 List 型態的 Monoid 時要怎麼做呢？我們始終可以用 map function 來轉換任何東西！

Exercise D23-1

實作 foldMap。

def foldMap[A, B](as: List[A], m: Monoid[B])(f: A => B): B

關聯性和平行性

如果是 Monoid 的 foldLeft 和 foldRight，我們其實可以用平衡的方式來 fold List，這可以讓它更有效率且能支援平行化運算，

假設我們有 a, b, c, d，如果我們用 Monoid 來做 foldLeft 的話會是這樣，

combine(combine(combine(a, b), c), d)

但如果用平衡方式來做的話會這樣，

combine(combine(a, b), combine(c, d))

此時就可以對裡面 2 個 combine 平行化運算，因為它們是彼此獨立計算的，越平衡的樹在處理上會越有效率，可以想像成把 List 變成 二元平衡樹 (balanced binary tree)。

二元平衡樹中任意一個節點的左右子樹的高度相差不能大於 1 。

Exercise D23-2

用 indexedSeq 來實作平衡版本的 foldMap。

Scala 的 indexedSeq 在把 2 個 Seq 對半切時會更有效率，且也支持的 random access。

def foldMapV[A, B](as: IndexedSeq[A], m: Monoid[B])(f: A => B): 

明天繼續啦！

Day 23 - Exercise answer